package com.datastructures2.sanlieTable;

import com.datastructures2.search.SequentialSearchST;

import java.util.NoSuchElementException;

/**
 * 在键的顺序不重要的应用中，该基于拉链法的散列可能是最快最广泛的实现
 * @author MaoLin Wang
 * @date 2020/3/221:22
 */
public class SeparateChainingHashST<Key,Value> {
    /**
     * 键值对总数
     */
    private int N;
    /**
     * 散列表大小
     */
    private int M;

    private SequentialSearchST<Key,Value>[] st;

    public SeparateChainingHashST() {
        this(997);
    }

    public SeparateChainingHashST(int M) {
        this.M=M;
        st=new SequentialSearchST[M];
        for (int i = 0; i < M; i++) {
            st[i]=new SequentialSearchST<>();
        }
    }

    private void resize(int capacity){
        SeparateChainingHashST<Key,Value>hashST=new SeparateChainingHashST<>(capacity);
        for (int i = 0; i < M; i++) {
            for (Key key:st[i].keys()){
                if (key!=null){
                    hashST.put(key,st[i].get(key));
                }
            }
        }
        this.M=hashST.M;
        this.N=hashST.N;
        this.st=hashST.st;
    }
    private int hash(Key key){
        return (key.hashCode() & 0x7fffffff) % M;
    }
    public Value get(Key key){
        if (key == null) throw new IllegalArgumentException("argument to get() is null");

        return st[hash(key)].get(key);
    }

    /**
     * 删除指定键值对
     * @param key
     */
    public void delete(Key key) {
        if (key == null) throw new IllegalArgumentException("argument to delete() is null");

        int i = hash(key);
        if (st[i].contains(key)){
            N--;
        }
        st[i].delete(key);
        //保证链表平均长度在2到8间 此为下界2
        if (N>0 && N<=M*2){
            resize(M/2);
        }

    }
    public boolean contains(Key key) {
        if (key == null) throw new IllegalArgumentException("key为空");
        return get(key) != null;
    }

    public void put(Key key,Value value){
        if (key==null){
            throw new NoSuchElementException("key为空");
        }
        if (value==null){
            delete(key);
        }
        //保证链表的长度在2到8之间
        if (N>=8*M){
            resize(M*2);
        }
        st[hash(key)].put(key,value);
    }
    public int size() {
        return N;
    }
    public boolean isEmpty() {
        return size() == 0;
    }
}
